package com.buaa.leecode;

import java.util.LinkedList;

/**
 * Convert Sorted Array to Binary Search Tree
 */
public class N108 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    int count = 0;

    private void bfsTreeNode(LinkedList<TreeNode> queue) {
        if (queue.isEmpty()) {
            return;
        }
        TreeNode top = queue.poll();
        System.out.print("," + top.val);
        int flag = 0;
        if (top.left != null) {
            queue.add(top.left);
            flag++;
        }
        if (top.right != null) {
            queue.add(top.right);
            flag++;
        }
        if (flag == 1) {
//            System.out.print(",null");
        }
        bfsTreeNode(queue);
    }

    private TreeNode buildNode(int[] nums, int start, int end) {
        if (nums.length <= 0 || start > end) {
            return null;
        }
        int middle = start + (end - start ) / 2;
        System.out.println(count + " 取中间数：" + middle + "=>" + nums[middle]);
        count++;
        TreeNode node = new TreeNode(nums[middle]);
        node.left = buildNode(nums, start, middle - 1);
        node.right = buildNode(nums, middle + 1, end);
        return node;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode node = buildNode(nums, 0, nums.length - 1);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        bfsTreeNode(queue);
        return node;
    }

    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        new N108().sortedArrayToBST(nums);
    }

}
